|
The blossom algorithm is an algorithm in graph theory for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965.〔 〕 Given a general graph ''G'' = (''V'', ''E''), the algorithm finds a matching ''M'' such that each vertex in ''V'' is incident with at most one edge in ''M'' and |''M''| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph. A major reason that the blossom algorithm is important is that it gave the first proof that a maximum-size matching could be found using a polynomial amount of computation time. Another reason is that it led to a linear programming polyhedral description of the matching polytope, yielding an algorithm for min-''weight'' matching.〔 〕 As elaborated by Alexander Schrijver, further significance of the result comes from the fact that this was the first polytope whose proof of integrality "does not simply follow just from total unimodularity, and its description was a breakthrough in polyhedral combinatorics." ==Augmenting paths== Given ''G'' = (''V'', ''E'') and a matching ''M'' of ''G'', a vertex ''v'' is exposed if no edge of ''M'' is incident with ''v''. A path in ''G'' is an alternating path, if its edges are alternately not in ''M'' and in ''M'' (or in ''M'' and not in ''M''). An augmenting path ''P'' is an alternating path that starts and ends at two distinct exposed vertices. A matching augmentation along an augmenting path ''P'' is the operation of replacing ''M'' with a new matching . It may be proven that a matching ''M'' is maximum if and only if there is no ''M''-augmenting path in ''G''. Hence, either a matching is maximum, or it can be augmented. Thus, starting from an initial matching, we can compute a maximum matching by augmenting the current matching with augmenting paths as long as we can find them, and return whenever no augmenting paths are left. We can formalize the algorithm as follows: INPUT: Graph ''G'', initial matching ''M'' on ''G'' OUTPUT: maximum matching ''M *'' on ''G'' A1 function ''find_maximum_matching''( ''G'', ''M'' ) : ''M *'' A2 ''P'' ← ''find_augmenting_path''( ''G'', ''M'' ) A3 if ''P'' is non-empty then A4 return ''find_maximum_matching''( ''G'', augment ''M'' along ''P'' ) A5 else A6 return M A7 end if A8 end function We still have to describe how augmenting paths can be found efficiently. The subroutine to find them uses blossoms and contractions. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Blossom algorithm」の詳細全文を読む スポンサード リンク
|